#define _CRT_SECURE_NO_WARNINGS 1

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int maxArea(vector<int>& height)
    {
        int left = 0, right = height.size() - 1;
        int ret = 0;
        while (left < right)
        {
            int h = min(height[left], height[right]);
            ret = max(ret, h * (right - left));
            if (height[left] < height[right])
                left++;
            else
                right--;
        }
        return ret;
    }
};

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums)
    {
        sort(nums.begin(), nums.end(), less<int>());
        vector<vector<int>> ret;
        int left = 0, right = 0, line = nums.size() - 1;
        while (line >= 2)
        {
            left = 0, right = line - 1;
            int target = -nums[line];
            while (left < right)
            {
                if (nums[left] + nums[right] < target)
                    left++;
                else if (nums[left] + nums[right] > target)
                    right--;
                else
                {
                    vector<int> tmp;
                    tmp.emplace_back(nums[left]);
                    tmp.emplace_back(nums[right]);
                    tmp.emplace_back(nums[line]);
                    ret.push_back(tmp);

                    left++;
                    while (left < right && nums[left] == nums[left - 1])
                        left++;
                    right--;
                    while (left < right && nums[right] == nums[right + 1])
                        right--;
                }
            }
            line--;
            while (line >= 2 && nums[line] == nums[line + 1])
                line--;
        }
        return ret;
    }
};

class Solution {
public:
    int trap(vector<int>& height)
    {
        int left = 0, right = height.size() - 1;
        int leftMax = 0, rightMax = 0;
        int total = 0;
        while (left <= right)
        {
            if (leftMax < rightMax)
            {
                int rain = leftMax - height[left];
                if (rain < 0)
                    total += 0;
                else
                    total += rain;
                leftMax = max(leftMax, height[left]);
                left++;
            }
            else
            {
                int rain = rightMax - height[right];
                if (rain < 0)
                    total += 0;
                else
                    total += rain;
                rightMax = max(rightMax, height[right]);
                right--;
            }
        }
        return total;
    }
};